#include <iostream>
#include <vector>
using namespace std;

//int main()
//{
//    int i;
//    cin >> i;
//    int* p = new int[i];
//    for (int n = 0; n < i; n++)
//    {
//        cin >> p[n];
//    }
//    int key;
//    cin >> key;
//    int left = 0;
//    int right = i - 1;
//    int mix = (left + right) >> 1;
//    int prev = -1;
//    while (left < right)
//    {
//        if (p[mix] == key)
//        {
//            prev = mix + 1;
//            break;
//        }
//        else if (p[left] == key)
//        {
//            prev = left + 1;
//            break;
//        }
//        else if (p[right] == key)
//        {
//            prev = right + 1;
//            break;
//        }
//        else if (p[mix] > key)
//        {
//            right = mix;
//        }
//        else if (p[mix] > key)
//        {
//            left = mix;
//        }
//    }
//    if (prev == -1)
//    {
//        cout << "NOT FOUND" << endl;
//    }
//    else
//    {
//        cout << prev << endl;
//    }
//    return 0;
//}

//#define MAXSIZE 50
//typedef int KeyType;
//
//typedef  struct
//{
//    KeyType  key;
//} ElemType;
//
//typedef  struct
//{
//    ElemType* R;
//    int  length;
//} SSTable;
//
//void  Create(SSTable& T)
//{
//    int i;
//    T.R = new ElemType[MAXSIZE + 1];
//    cin >> T.length;
//    for (i = 1; i <= T.length; i++)
//        cin >> T.R[i].key;
//}
//
//int  Search_Bin(SSTable T, KeyType k)
//{
//    int left = 0;
//    int right = T.length;
//    int mix = (left + right) >> 1;
//    while (left < right)
//    {
//        if (T.R[left].key == k)
//        {
//            return left;
//        }
//        else if (T.R[mix].key == k)
//        {
//            return mix;
//        }
//        else if (T.R[right].key == k)
//        {
//            return right;
//        }
//        else if (T.R[mix].key > k)
//        {
//            right = mix;
//        }
//        else if (T.R[mix].key < k)
//        {
//            left = mix;
//        }
//        mix = (left + right) >> 1;
//    }
//    return 0;
//}
//
//int main()
//{
//    SSTable T;
//    KeyType k;
//    Create(T);
//    cin >> k;
//    int pos = Search_Bin(T, k);
//    if (pos == 0) cout << "NOT FOUND" << endl;
//    else cout << pos << endl;
//    return 0;
//}


//class Node {
//public:
//    int val;
//    Node* left;
//    Node* right;
//
//    Node() {}
//
//    Node(int _val) {
//        val = _val;
//        left = NULL;
//        right = NULL;
//    }
//
//    Node(int _val, Node* _left, Node* _right) {
//        val = _val;
//        left = _left;
//        right = _right;
//    }
//};
//
//class Solution {
//public:
//    Node* treeToDoublyList(Node* root) {
//        if (root == nullptr)
//        {
//            return nullptr;
//        }
//        DFS(root);
//        head->left = ped;
//        ped->right = head;
//        return head;
//    }
//    void DFS(Node* root)
//    {
//        if (root == nullptr)
//        {
//            return;
//        }
//        DFS(root->left);
//        if (head == nullptr)
//        {
//            head = ped = root;
//        }
//        else
//        {
//            root->left = ped;
//            ped->right = root;
//            ped = root;
//        }
//        DFS(root->right);
//    }
//private:
//    Node* head = nullptr;
//    Node* ped = nullptr;
//};
//
//class Node {
//public:
//    int val;
//    Node* next;
//    Node* random;
//
//    Node(int _val) {
//        val = _val;
//        next = NULL;
//        random = NULL;
//    }
//};
//
//class Solution {
//public:
//    Node* copyRandomList(Node* head) {
//        if (head == nullptr)
//        {
//            return nullptr;
//        }
//        Node* cur = head;
//        while (cur)
//        {
//            Node* node = new Node(cur->val);
//            node->next = cur->next;
//            cur->next = node;
//            cur = node->next;
//        }
//        cur = head;
//        this->NewNode = head->next;
//        Node* node = head->next;
//        while (cur && node)
//        {
//            if (cur->random == nullptr)
//            {
//                node->random = cur->random;
//            }
//            else
//            {
//                node->random = cur->random->next;
//            }
//            cur = node->next;
//            if (cur == nullptr)
//            {
//                break;
//            }
//            node = cur->next;
//        }
//        cur = head;
//        node = head->next;
//        while (cur && node)
//        {
//            cur->next = node->next;
//            cur = cur->next;
//            if (cur == nullptr)
//            {
//                break;
//            }
//            node->next = cur->next;
//            node = node->next;
//        }
//        return this->NewNode;
//    }
//private:
//    Node* NewNode = nullptr;
//};
//
//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int n = nums.size();
//        if (n < 2)
//        {
//            return n;
//        }
//        int fast = 2;
//        int slow = 2;
//        while (fast < n)
//        {
//            if (nums[slow - 2] != nums[fast])
//            {
//                nums[slow] = nums[fast];
//                slow++;
//            }
//            fast++;
//        }
//        return slow;
//    }
//};
//
//class Solution {
//public:
//    int majorityElement(vector<int>& nums) {
//        int n = nums[0];
//        int i = 0;
//        for (int y = 0; y < nums.size(); y++)
//        {
//            if (n == nums[y])
//            {
//                i++;
//            }
//            else
//            {
//                i--;
//            }
//            if (i < 0)
//            {
//                n = nums[y];
//                i = 0;
//            }
//        }
//        return n;
//    }
//};
//
//class Solution {
//public:
//    void rotate(vector<int>& nums, int left, int right)
//    {
//        while (left < right)
//        {
//            int k = nums[left];
//            nums[left] = nums[right];
//            nums[right] = k;
//            left++;
//            right--;
//        }
//    }
//    void rotate(vector<int>& nums, int k)
//    {
//        int n = nums.size();
//        k %= n;
//        rotate(nums, k, n - 1);
//        rotate(nums, 0, k - 1);
//        rotate(nums, 0, n - 1);
//
//    }
//};
//
//class Solution {
//public:
//    void rotate(vector<int>& nums, int k) {
//        int n = nums.size();
//        k %= n;
//        while (k)
//        {
//            int p = nums[n - 1];
//            for (int i = n - 1; i > 0; i--)
//            {
//                nums[i] = nums[i - 1];
//            }
//            nums[0] = p;
//            k--;
//        }
//    }
//};
//
//class Solution {
//public:
//    void rotate(vector<int>& nums, int k) {
//        int n = nums.size();
//        k %= n;
//        int* p = new int[n];
//        int n1 = 0;
//        for (int n2 = n - k; n2 < n; n2++)
//        {
//            p[n1++] = nums[n2];
//        }
//        for (int n2 = 0; n2 < n - k; n2++)
//        {
//            p[n1++] = nums[n2];
//        }
//        for (int i = 0; i < n; i++)
//        {
//            nums[i] = p[i];
//        }
//    }
//};
//
//int main()
//{
//    vector<int>  nums = { 1,2,3,4,5,6 ,7 };
//    Solution so;
//    so.rotate(nums, 3);
//    for (vector<int>::iterator it = nums.begin(); it < nums.end(); it++)
//    {
//        cout << *it << " ";
//    }
//    return 0;
//}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = (int)prices.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                ans = max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = (int)prices.size();
        int max = 0;
        int min = prices[0];
        for (int i = 1; i < n; i++)
        {
            if (prices[i] - min > max)
            {
                max = prices[i] - min;
            }
            if (min > prices[i])
            {
                min = prices[i];
            }
        }
        return max;
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int mn = m + n - 1;
        m -= 1;
        n -= 1;
        while (m >= 0 && n >= 0)
        {
            if (nums1[m] > nums2[n])
            {
                nums1[mn--] = nums1[m--];
            }
            else
            {
                nums1[mn--] = nums2[n--];
            }
        }
        while (m >= 0)
        {
            nums1[mn--] = nums1[m--];
        }
        while (n >= 0)
        {
            nums1[mn--] = nums2[n--];
        }
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        int fast = 0;
        while (fast < nums.size())
        {
            while (fast < nums.size() && nums[fast] == val)
            {
                fast++;
            }
            if (fast < nums.size())
            {
                nums[slow++] = nums[fast++];
            }
        }
        return slow;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int fast = 1;
        int slow = 0;
        int n = size(nums);
        while (fast < n)
        {
            while (fast < n && nums[fast] == nums[slow])
            {
                fast++;
            }
            if (fast < n)
            {
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i)
        {
            ans += max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
};

class Solution {
public:
    bool Jump(vector<int>& nums, int i, int n)
    {
        if (i == n)
        {
            return true;
        }
        int k = nums[i];
        if (i + k >= n)
        {
            return true;
        }
        while (0 <= k)
        {
            if (Jump(nums, i + k, n))
            {
                return true;
            }
            k--;
        }
        return false;
    }
    bool canJump(vector<int>& nums) 
    {
        return Jump(nums, 0, nums.size() - 1);
    }
};

class Solution {
public:

    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int k = 0;
        for (int i = 0; i < n; i++)
        {
            if (i > k)
            {
                return false;
            }
            k = max(k, i + nums[i]);
        }
        return true;
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int k = 0;
        int ret = 0;
        int Max = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (Max >= i)
            {
                Max = max(Max, i + nums[i]);
                if (i == k)
                {
                    k = Max;
                    ret++;
                }
            }
        }
        return ret;
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int h = 0;
        int n = citations.size() - 1;
        while (n >= 0 && citations[n] > h)
        {
            h++;
            n--;
        }
        return h;
    }
};